package com.mrzhou.study.struct.stack;

import com.mrzhou.study.struct.support.CharStack;
import com.mrzhou.study.struct.support.CalculateUtil;
import com.mrzhou.study.struct.support.NumStack;

/**
 * 栈的应用之~模拟计算器(处理简单的算术运算)
 *  示例: "8-9/3+6*5" 字符的算术字符计算出来
 *      注: 在测试时使用示例中的算式来进行检查
 */
public class ComputeSimple {

    /**
     * 处理普通的算术字符串
     */
    public static int compute(String str) {
        // 1.) 创建两个栈(数值栈和运算符号栈)
        NumStack numStack = new NumStack(50); // 保存算术中的数字
        CharStack charStack = new CharStack(50); // 保存算术中的运算符
        char[] chars = str.toCharArray(); // 将算术运算符转换成char数组
        int i = 0; // 算术char数组遍历指针
        String num = "";
        while(chars.length != i) { // 遍历整个算术运算符
            char c = chars[i];
            if(numStack.isDigit(c) && i != chars.length-1 && numStack.isDigit(chars[i+1]) ) {
                num+=chars[i];
            } else if(charStack.isLegalChar(c)) { // 如果是算术运算中合法字符, 要压入符号栈
                if(charStack.isEmpty()) { // 如果符号栈空, 则直接压入
                    charStack.push(c);
                } else {
                    if(c == ')') { // 应括号的优先级最高, 所以需要计算出括号中的全部数据
                       char peek = charStack.pop(); // 取出当前的操作符
                        while(peek != '(') {
                            int var1 = numStack.pop();
                            int var2 = numStack.pop();
                            numStack.push(CalculateUtil.choose(var2, var1, peek));
                            peek = charStack.pop();
                        }
                        i++;
                        continue;
                    }

                    // 注: 在运算符压入栈前, 必须判断当前栈顶的优先级, 因此此处需要while循环
                    // 如果即将插入的运算符优先级小于等于target的优先级
                    char target = charStack.peek(); // 拿到当前符号栈顶的数据
                    while(!charStack.isEmpty() && charStack.isOpers(c, target) && charStack.priority(c) <= charStack.priority(target) ) {
                        // 一次取出数字栈两个数 , 使用target相加, 后将计算结果压入数字栈, 然后将c压入符号栈
                        int var1 = numStack.pop();
                        int var2 = numStack.pop();
                        int result = CalculateUtil.choose(var2, var1, charStack.pop()); // 考虑到减法和除法操作, 这里必须是var2 - var1
                        numStack.push(result);
                        target = charStack.peek();
                    }
                    charStack.push(c);
                }
            } else if (numStack.isDigit(c)) {
                numStack.push(Integer.parseInt(num + c));
                num = "";
            }
            i++;
        }

        // 将数字栈和符号栈的结果进行最后一次的计算
        while(!charStack.isEmpty()) {
            int var1 = numStack.pop();
            int var2 = numStack.pop();
            numStack.push(CalculateUtil.choose(var2, var1, charStack.pop()));
        }
        return numStack.pop(); // 最后得到算术的结果
    }

    public static void main(String[] args) {
        String str = "(5*((7+ 7*4 - 4 +8*9)/(3+4))) + 1 * 8";
        int i = (5*((7+ 7*4 - 4 +8*9)/(3+4))) + 1 * 8;
        System.out.printf("%s = %d; i = %d\n", str, ComputeSimple.compute(str), i);
    }

}
